In recent years, as the field of communications such as mobile communications and deep-space communications, and the field of broadcast such as ground-wave broadcast and satellite digital broadcast are studied with remarkable progress, for example, the coding theory is actively studied to increase the efficiency of error-correction encoding and decoding.
Shannon limit presented by so-called Shannon (C. E. Shannon) communication-path encoding theorem is known, as the theoretical limits of code performance. The coding theory is studied for developing a code that presents performance approaching the above-described Shannon limit. In recent years, a method referred to as so-called turbo coding including parallel concatenated convolutional codes (PCCC), serially concatenated convolutional codes (SCCC), and so forth, was developed, as an encoding method that presents performance approaching Shannon limit. Further, aside from the turbo codes being developed, a known encoding method, that is, low-density parity check codes (hereinafter referred to as LDPC codes) are receiving attention.
The LDPC code was suggested first time in “R. G. Gallager, “Low Density Parity Check Codes”, Cambridge, Mass.: M.I.T.Press, 1963” by R. G. Gallager. Then, the LDPC code receives further attention by “D. J. C. MacKay, “Good error correcting codes based on very sparse matrices”, Submitted to IEEE Trans. Inf. Theory, IT-45, pp. 399-431, 1999, “M. G. Luby M. Mitzenmacher, M. A. Shokrollahi and D. A. Spielman, “Analysis of low density codes and improved designs using irregular graphs”, in Proceedings of ACM Symposium on Theory of Computing, pp. 249-258, 1998”, and so forth.
According to studies in recent years, the performance of the LDPC code approaches Shannon limit with increases in the code length. Further, since the minimum distance of the LDPC code is proportional to the code length, the LDPC code has the following advantages, as its features. That is to say, the LDPC code has high block-error probability qualities and hardly causes a so-called error-floor phenomenon that is observed in qualities of decoding turbo codes or the like.
The above-described LDPC code will be described in detail, as below. The LDPC code is a linear code and not necessarily binary. However, in this specification, it will be described on the assumption that the LDPC code is binary.
The major characteristic of the LDPC code is that a parity check matrix defining the LDPC code is sparse. Here, the sparse matrix denotes a matrix including very few components whose values are “1”. The sparse check matrix is designated by reference character H. The sparse check matrix includes HLDPC shown in FIG. 1, where Hamming weight (the number of “1”) of each row is “2” and that of each column is “4”, for example.
Thus, the LDPC code defined by a check matrix H, where Hamming weight of each of the rows and columns is constant, is referred to as a regular LDPC code. On the other hand, an LDPC code defined by a check matrix H, where Hamming weight of each of the rows and columns is not constant, is referred to as an irregular LDPC code.
Encoding by using the above-described LDPC code is achieved by a generating generation matrix G based on the check matrix H and generating a code word by multiplying the generation matrix G by binary-data message. More specifically, first, an encoder for performing encoding by the LDPC code calculates the generation matrix G, where an equation GHT=0 holds, between the check matrix H and a transposed matrix HT. Where the generation matrix G is a k×n matrix, the encoder multiplies the generation matrix G by a k-bit data message (vector u) and generates an n-bit code word c (=uG). In the code word generated by the encoder, a code bit whose value is “0” is mapped to “+1” and a code bit whose value is “1” is mapped to “1”. Then, the code word is transmitted and received on the reception side via a predetermined communication path.
Decoding of the LDPC code can be performed by using an algorithm named and proposed by Gallager, as probabilistic decoding, that is, a message passing algorithm by belief propagation on a so-called Tanner graph including a variable node (sometimes referred to as a message node) and a check node. Hereinafter, the variable node and the check node are simply referred to as nodes, as required.
For example, the parity check matrix HLDPC shown in FIG. 1 is expressed by a Tanner graph shown in FIG. 2. In the Tanner graph shown in FIG. 2, each column of the parity check matrix HLDPC shown in FIG. 1 is determined to be a variable node and each row is determined to be a check node. Further, the j-th variable node and the i-th check node are connected to an element whose value is “1” on the i-th row and the j-th column of the parity check matrix HLDPC, as edges.
However, where the probability decoding is performed, the value of a message transmitted between the nodes is given, as a real number. Subsequently, there is a need to track the probability distribution of messages having consecutive values for analytical solution, which is extremely difficult. Therefore, Gallager proposed algorithms A and B, as an algorithm for decoding the LDPC code.
Usually, the LDPC-code decoding is achieved by performing procedures shown in FIG. 2. Here, in this case, a reception value (a received code sequence) is determined to be U0(u0i), a message transmitted from the check node is determined to be uj, and a message transmitted from the variable node is determined to be vi. Further, in this case, the message is a real-number value indicating the probability that the value is “0”, as a so-called log likelihood ratio.
Usually, decoding the LDPC code is achieved by performing procedures shown in FIG. 3. Here, in this case, the reception value (the received code sequence) is determined to be U0(u0i), the message transmitted from the check node is determined to be uj, and the message transmitted from the variable node is determined to be vi. Further, in this case, the message is the real-number value indicating the probability that the value is “0”, as the so-called log likelihood ratio.
First, for decoding the LDPC code, a reception value U0(u0i) is received, a message uj is initialized to “0”, and a variable k that is an integer functioning as a counter of repetition processing is initialized to “0”, at step S1, and the processing advances to step S2, as shown in FIG. 3. At step S2, the message vi is obtained by performing calculation shown by Equation (1) (variable-node calculation) based on the reception value U0(u0i), and the message uj is obtained by performing calculation shown in Equation (2) (check-node calculation) based on the message vi.
                              v          i                =                              u                          0              ⁢              i                                +                                    ∑                              j                =                1                                                              d                  v                                -                1                                      ⁢                          u              j                                                          Equation        ⁢                                  ⁢                  (          1          )                                                  tanh          ⁡                      (                                          u                j                            2                        )                          =                              ∏                          i              =              1                                                      d                c                            -              1                                ⁢                      tanh            ⁡                          (                                                v                  i                                2                            )                                                          Equation        ⁢                                  ⁢                  (          2          )                    
Here, dv and dc shown in Equations (1) and (2) are parameters that indicate the number of “1” along the vertical direction (columns) and the horizontal direction (rows) of the check matrix H and that can be arbitrarily selected, respectively. For example, in the case of a code (3, 6), equations dv=3 and dc=6 hold.
Further, in the calculations shown by Equations (1) and (2), a message input from an edge for outputting messages (a line connecting the variable node to the check node) is not used, as a parameter of sum operation or product operation. Therefore, the area of sum or product operation is determined to be 1 to dv−1, or 1 to dc−1. Further, the calculation shown in Equation (2) is actually performed by generating a table of a function R(v1, v2) shown in Equation (3) defined by one output for two inputs v1 and v2 in advance, and using the table consecutively (recursively), as shown in Equation (4).x=2 tan h−1{tan h(v1/2)tan h(v2/2)}=R(v1, v2)   Equation (3)uj=R(v1, R(v2, R(v3, . . . , R(vdc−2, vdc−1))))  Equation (4)
At step S2, further, the variable k is incremented by “1”, and the processing advances to step S3. At step S3, it is determined whether or not the variable k is larger than a predetermined repetition-decoding number N. Where it is determined that the variable k is not larger than N, at step S3, the processing returns to step S2, and the same processing is repeated thereafter.
Further, where it is determined that the variable k is larger than N, at step S3, the processing advances to step S4, so that the calculation shown in Equation (5) is performed, whereby the message vi is obtained and output, as a decoding result that is finally output. Then, the LDPC-code decoding is finished.
                              v          i                =                              u                          0              ⁢              i                                +                                    ∑                              j                =                1                                            d                v                                      ⁢                          u              j                                                          Equation        ⁢                                  ⁢                  (          5          )                    
Here, different from the calculation shown in Equation (1), the calculation shown in Equation (5) is performed by using messages input from all the edges connected to the variable node.
Where the LDPC-code decoding is performed by using the code (3, 6), for example, messages are transmitted between the nodes, as shown in FIG. 4. Further, the calculation shown in Equation (1) is performed at nodes indicated by signs “=” (variable nodes) shown in FIG. 4 and the calculation shown in Equation (2) is performed at nodes indicated by signs “+” (check nodes). Particularly, in the case of an algorithm A, the messages are divided into two and an exclusive OR operation is performed for dc−1 input messages at the nodes indicated by the signs “+”. Where all the bit values of dv−1 input messages are different from one another for a reception value R at the nodes indicated by the signs “=”, the code is reversed and output.
Aside from the above-described technology, in recent years, methods for mounting the LDPC-code decoding are studied. First, the LDPC-code decoding will be schematically described before describing the mouthing method.
FIG. 5 is an example parity check matrix of the LDPC code (3, 6) (where the encoding ratio is ½ and the code length is 12). The parity check matrix of the LDPC code can be written through a Tanner graph, as shown in FIG. 6. Here, in FIG. 6, check nodes are indicated by signs “+” and variable nodes are indicated by signs “=”. The check nodes and the variable nodes correspond to the rows and columns of the parity check matrix, respectively. Connections between the check nodes and the variable nodes are edges and correspond to “1” of the parity check matrix. That is to say, where a component in the j-th row and the i-th column of the parity check matrix is one, the i-th variable node (a node indicated by the sign “=”) from top and the j-th check node (a node indicated by the sign “+”) from top are connected to each other by the edge, as shown in FIG. 6. The edge indicates that a code bit corresponding to the variable node has a constraint condition corresponding to the check node. Further, FIG. 6 shows the Tanner graph of the parity check matrix shown in FIG. 5.
A sum product algorithm can be used, as the LDPC-code decoding method (Refer to “Tadashi Wadayama, “Low density parity check code and sum-product algorithm”, Jun. 22, 2001, Okayama Prefectural University”, for example).
According to the sum product algorithm, the variable-node operation and the check-node operation are performed repetitively.
At the variable node, the operation shown in Equation (1) (the variable-node operation) is performed, as shown in FIG. 7. That is to say, according to FIG. 7, the message vi corresponding to an edge for which a calculation is to be performed is calculated by using messages u1 and u2 transmitted from the other edges connected to the variable node and the reception data u0i. Messages corresponding to the other edges are calculated in the same manner.
Next, Equation (2) is rewritten by using the relation expressed by the equation a×b=exp{ln(|a|)+ln(|b|)}×sign(a)×sign(b), as shown by Equation (6), before describing the check-node operation. Here, where the expression x≧0 holds, the sign(x) is one, and where the expression x<0 holds, the sign(x) is negative one.
                                                                        u                j                            =                            ⁢                              2                ⁢                                                      tanh                                          -                      1                                                        ⁡                                      (                                                                  ∏                                                  i                          =                          1                                                                                                      d                            c                                                    -                          1                                                                    ⁢                                              tanh                        ⁡                                                  (                                                                                    v                              i                                                        2                                                    )                                                                                      )                                                                                                                          =                            ⁢                              2                ⁢                                                      tanh                                          -                      1                                                        [                                      exp                    ⁢                                          {                                                                        ∑                                                      i                            =                            1                                                                                                              d                              c                                                        -                            1                                                                          ⁢                                                  ln                          ⁡                                                      (                                                                                                                        tanh                                ⁡                                                                  (                                                                                                            v                                      i                                                                        2                                                                    )                                                                                                                                                    )                                                                                              }                                        ×                                                                                                                                        ⁢                                                ∏                                      i                    =                    1                                                                              d                      c                                        -                    1                                                  ⁢                                  sign                  ⁡                                      (                                          tanh                      ⁡                                              (                                                                              v                            i                                                    2                                                )                                                              )                                                              ]                                                                          =                            ⁢                              2                ⁢                                                      tanh                                          -                      1                                                        ⁡                                      [                                          exp                      ⁢                                              {                                                  -                                                      (                                                                                          ∑                                                                  i                                  =                                  1                                                                                                                                      d                                    c                                                                    -                                  1                                                                                            ⁢                                                              -                                                                  ln                                  ⁡                                                                      (                                                                          tanh                                      ⁡                                                                              (                                                                                                                                                                                                                        v                                              i                                                                                                                                                                            2                                                                                )                                                                                                              )                                                                                                                                                        )                                                                          }                                                              ]                                                  ×                                                                                                      ⁢                                                ∏                                      i                    =                    1                                                                              d                      c                                        -                    1                                                  ⁢                                  sign                  ⁡                                      (                                          v                      i                                        )                                                                                                          Equation        ⁢                                  ⁢                  (          6          )                    
Further, where the expression x≧0 holds and φ(x) is defined as ln(tan h(x/2)), the expression φ−1(x)=2 tan h−1(e−x) holds. Therefore, Equations (6) can be written, as shown by Equation (7).
                              u          j                =                                            ϕ                              -                1                                      ⁡                          (                                                ∑                                      i                    =                    1                                                                              d                      c                                        -                    1                                                  ⁢                                  ϕ                  ⁡                                      (                                                                                        v                        i                                                                                    )                                                              )                                ×                                    ∏                              i                =                1                                                              d                  c                                -                1                                      ⁢                          sign              ⁡                              (                                  v                  i                                )                                                                        Equation        ⁢                                  ⁢                  (          7          )                    
The operation shown in Equation (7) (check-node operation) is performed, at the check node, as shown in FIG. 8. That is to say, in FIG. 8, the message uj corresponding to an edge for which a calculation is to be performed is calculated by using messages v1, v2, v3, v4, and v5 transmitted from the other edges connected to the check node. Messages corresponding to the other edges are calculated in the same manner.
Further, the function φ(x) can be expressed, as the equation φ(x)=ln((ex+1)/(ex−1)). Further, the function φ(x) can be expressed, as the equation φ(x)=φ−1(x), where the expression x>0 holds. The functions φ(x) and φ−1(x) are often mounted on hardware by using an LUT (look up table). The same LUT can be used for both the functions.
Where the sum product algorithm is mounted on hardware, the variable-node operation shown in Equation (1) and the check-node operation shown in Equation (7) need to be performed repetitively by using a circuit with suitable size and at suitable operation frequencies.
Further, methods for calculating the cost of LDPC-code operation using the above-described sum product algorithm are widely known (Refer to “Matthew C. Davey, David J C MacKay “Low Density Parity Check Codes over GF(q)””, for example.).
For obtaining high decoding qualities by using the sum product algorithm (SPA) as described above, the density of the parity check matrix must be low.
Further, FIG. 9 shows a parity check matrix H of the other ordinary linear code, such as a Reed-Solomon code, where the primitive root of a definition field is determined to be a. Usually, the density of the parity check matrix H of a linear code is not low, as shown in FIG. 9. For the Reed-Solomon code whose density is not low, decoding using Euclid's algorithm or the like (hereinafter referred togas ordinary decoding) is performed.
FIG. 10 is a block diagram illustrating the configuration of an example error-correction system for performing error correction by using the Reed-Solomon code. The error-correction system shown in FIG. 10 is a system used for a digital-communication system such as a digital TV, for example.
In the error-correction system shown in FIG. 10, digital data transmitted from an encoder 10 on the transmission side is transmitted to a decoder 30 on the reception side via a communication path 21 such as the Internet, for example.
The encoder 10 includes a Reed-Solomon encoding unit 11 for encoding externally transmitted digital data for transmission by using the Reed-Solomon code, an interleaver 12 for rearranging the encoded digital data, a convolutional-encoding unit 13 for performing convolutional encoding, and a communication processing unit 14 for communicating with the decoder 30 via the communication path 21.
Further, the decoder 30 includes a communication processing unit 31 for obtaining a transmission word transmitted via the communication path 21, a convolutional-decoding unit 32 for performing convolutional decoding for the obtained transmission word, a deinterleaver 33 for resetting the rearranged data to the original order, and a Reed-Solomon decoding unit 34 for performing Reed-Solomon decoding (ordinary decoding).
The transmission digital data transmitted from outside the encoder 10 is encoded into a Reed-Solomon code through the Reed-Solomon encoding unit 11 of the encoder 10 and transmitted to the interleaver 12. The interleaver 12 performs data rearranging (interleaving) for diffusing burst errors that occur mainly in the communication path 21. Since the Reed-Solomon code performs error correction, where a plurality of bits is regarded as a single symbol, the interleaver 12 performs symbol interleaving for diffusing the burst errors per symbol.
The rearranged transmission digital data is further subjected to convolutional encoding through the convolutional-encoding unit 13 based on a plurality of data blocks so that code sequences are determined in sequence. For example, upon receiving the digital data for each k-bit data block from the interleaver 12, the convolutional-encoding unit 13 with a constraint length K encodes the digital data to an n-bit code block based on not only the data block transmitted at that time but also K data blocks including data blocks that had been provided.
Then, the convolutional-encoded digital data is converted to data that can be transmitted through the communication processing unit 14 and transmitted to the decoder 30 via the communication path 21.
The decoder 30 obtains the transmission word transmitted via the communication path 21 wired or unwired in the communication processing unit 31. The obtained transmission word is subjected to convolutional decoding through the convolutional-decoding unit 32. Upon receiving the convolutional-decoded data, the deinterleaver 33 performs processing for resetting the rearranged data to the original order (deinterleaving) through rearranging the data according to a method corresponding to the interleaving performed by the interleaver 12 of the encoder. The Reed-Solomon decoding unit 34 performs Reed-Solomon decoding by ordinary decoding for the digital data reset to the original order, reconstitutes the digital data in the previous state where Reed-Solomon encoding is not yet performed, and transmits the data to outside the decoder 30.
In the above-described manner, the error correction system shown in FIG. 10 corrects errors occur during communications and performs communications more precisely than ever.
FIG. 11 is a block diagram illustrating the configuration of an example recording-and-reproducing apparatus using the error correction system for performing the error correction by using the Reed-Solomon code. The recording-and-reproducing apparatus shown in FIG. 11 is a digital-recording-medium recording-and-reproducing apparatus such as a DVD (Digital Versatile Disc) record player, for example.
The recording-and-reproducing apparatus 50 shown in FIG. 11 encodes the externally transmitted digital data through the encode-processing unit 60 and records the digital data onto a recording medium 72 in a recording-and-reproducing unit 70. Further, the recording-and-reproducing apparatus 50 reproduces the digital data recorded on the recording medium 72 in the recording-and-reproducing unit 70, obtains the original digital data through performing decoding in a decoding unit 80, and externally outputs the data.
The encode-processing unit 60 includes first to n-th Reed-Solomon encoding units 61-1 to 61-n for performing Reed-Solomon encoding for the digital data, where the Reed-Solomon encoding relates to degrees that are different from one another.
The recording-and-reproducing unit 70 includes a recording unit 71 for recording the data transmitted from the encode-processing unit 60 onto the recording medium 72, the recording medium 72 such as an optical disk, for example, and a reproducing unit 73 for reproducing the data recorded on the recording medium 72.
Further, the decode-processing unit 80 is a decoder corresponding to the encode-processing unit 60 and includes first to n-th Reed-Solomon decoding units 81-1 to 81-n for performing Reed-Solomon decoding (ordinary decoding) relating to degrees that are different to one another for the digital data.
The digital data transmitted from outside the encode-processing unit 60 is subjected to Reed-Solomon encoding relating to degree one in the first Reed-Solomon encoding unit 61-1. Then, the digital data is sequentially subjected to Reed-Solomon encoding relating to each of degrees two to n in the second to n-th Reed-Solomon encoding units 61-2 to 61-n. Where the n-th Reed-Solomon encoding unit 61-n finishes encoding, the encode-processing unit 60 transmits the encoded digital data to the recording-and-reproducing unit 70. The recording unit 71 of the recording-and-reproducing unit 70 records the digital data transmitted from the encode-processing unit 60 onto the recording medium 72.
The reproducing unit 73 of the recording-and-reproducing unit 70 reproduces the digital data recorded on the recording medium 72 (the encoded digital data) and transmits the digital data to the decode-processing unit 80.
The decode-processing unit 80 performs Reed-Solomon decoding (ordinary decoding) relating to each degree for the digital data transmitted from the reproducing unit 73 in the first to n-th Reed-Solomon decoding units 81-1 to 81-n and reconstitutes the original digital data. Further, the decode-processing unit 80 performs decoding that is the reverse of decoding performed by the encode-processing unit 60. First, the decode-processing unit 80 performs decoding relating to degree n in the n-th Reed-Solomon decoding unit 81-n, and subsequently performs the Reed-Solomon decoding in decreasing order of degrees, that is, from degree n-1 to degree n-2. Finally, the decode-processing unit 80 performs decoding relating to the first degree. The decode-processing unit 80 outputs the reconstituted original digital data to outside the recording-and-reproducing apparatus 50.
As has been described, the recording-and-reproducing apparatus 50 shown in FIG. 11 corrects data errors that occur during data recording or reproducing.
The ordinary decoding for the above-described Reed-Solomon code, a BCH (Bose-Chaudhuri-Hocquenghem) code, and so forth, is a decoding method used for a hard-decision reception word where a reception value is estimated to be only “0” or “1”.
However, where a soft-decision reception word is obtained and where a Reed-Solomon code is subjected to the ordinary decoding in a system that can obtain the soft-decision reception word, the decoding quality is low. This is because the decoding quality obtained by using the hard-decision reception word is usually lower than in the case where the soft-decision reception word is used.
Subsequently, the above-described method for decoding by using the sum product algorithm is considered. However, since the density of a parity check matrix of a widely-used linear code is not low in most cases, the decoding quality does not increase. Further, if the density of a provided parity check matrix was low, the configuration of a sum product algorithm on a large finite field would be much complicated, which would increase the operation cost.